CountNumberOfBinaryStrings.java

packagesection19_DynamicProgramming;

/*
count no. of binary Strings of length N such that there are no consecutive 1's
present inside String
*/

publicclassCountNumberOfBinaryStrings {

publicstaticvoidmain(String[] args) {

intlength = 3;
System.out.println(countBinaryStr(length)); // 5

System.out.println(countBinaryStr(1)); // 2
System.out.println(countBinaryStr(2)); // 3
 }

publicstaticintcountBinaryStr(intn) {
// array of bits ending in zero
int[] zeros = newint[n];
// array of bits ending in one
int[] ones = newint[n];

// seed values
// since no. of binary strings of length 1 ending in zero is 1
zeros[0] = 1;
// since no. of binary strings of length 1 ending in one is 1
ones[0] = 1;

for (intindex = 1; index < zeros.length; index++) {
zeros[index] = zeros[index - 1] + ones[index - 1];
ones[index] = zeros[index - 1];
 }

returnzeros[n - 1] + ones[n - 1];
 }
}